﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/k-th-smallest-prime-fraction/
/*
题目描述：
给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数  组成，且其中所有整数互不相同。
对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。
那么第 k 个最小的分数是多少呢?  以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。

 
示例 1：
输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5

示例 2：
输入：arr = [1,7], k = 1
输出：[1,7]
 

提示：
2 <= arr.length <= 1000
1 <= arr[i] <= 3 * 104
arr[0] == 1
arr[i] 是一个 素数 ，i > 0
arr 中的所有数字 互不相同 ，且按 严格递增 排序
1 <= k <= arr.length * (arr.length - 1) / 2
 
进阶：你可以设计并实现时间复杂度小于 O(n2) 的算法解决此问题吗？
*/

// 方法1——二分法+双指针
int* kthSmallestPrimeFraction(int* arr, int arrSize, int k, int* returnSize) {
    double left = 0.0;
    double mid = 0.0;
    double right = 1.0;
    int* answer = (int*)malloc(2 * sizeof(int));
    if (NULL == answer) {
        perror("malloc fail!\n");
        exit(-1);
    }
    *returnSize = 2;
    int i = 0;
    int j = 0;
    int count = 0;
    int x = 0;
    int y = 1;
    while (1) {
        mid = left + (right - left) / 2;
        count = 0;
        i = -1;
        x = 0;
        y = 1;
        for (j = 1; j < arrSize; j++) { // 枚举分母，arr[j]即为分母
            while ((double)arr[i + 1] / arr[j] < mid) { // 枚举分子，arr[i + 1]即为分子
                i++;
                if (arr[i] * y > arr[j] * x) { // 即x/y < i / j时候就要更新x 和 y
                    x = arr[i];
                    y = arr[j];
                }
            }
            count += i + 1;
        }
        if (count == k) {
            answer[0] = x;
            answer[1] = y;
            return answer;
        }
        if (count < k) {
            left = mid;
        }
        else {
            right = mid;
        }
    }
    return answer;
}


int main() {
    int nums[] = { 1, 2, 3, 5 };
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int k = 0;
    int returnSize = 0;
    int* answer = kthSmallestPrimeFraction(nums, numsSize, k, &returnSize);
    printf("[%d %d]", answer[0], answer[1]);
    return 0;
}